package j2024.j202409;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
class TreeNode {
  int val = 0;
  TreeNode left = null;
  TreeNode right = null;
  public TreeNode(int val) {
    this.val = val;
  }
}
public class j0926 {
    public static void main1(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        for (int i = 0; i < n; i++) {
            int tmp = in.nextInt();
            int ret = isOU(tmp);
            System.out.println(ret);
        }
    }
    public static int isOU(int a){
        if(a%2==0){
            return a;
        }
        boolean is = false;
        int ret = -1;
        ArrayList<Integer> list = new ArrayList<>();
        while(a!=0){
            if(a%2==0){
                is = true;
                break;
            }
            list.add(a%10);
            a/=10;
        }
        if(is){
            ret = Sum(list,a);
        }
        return ret;
    }
    public static int Sum(ArrayList<Integer> list,int a){
        int ttmp = a;
        int cou = 0;
        while(ttmp!=0){
            ttmp/=10;
            cou++;
        }
        int i = list.size()-1;
        int sq = (int) Math.pow(10,cou);
        while(i>=0){
            a+=list.get(i--)*sq;
            sq*=10;
        }
        return a;
    }

    public int retmax = Integer.MIN_VALUE;
    public int maxPathSum (TreeNode root) {
        dfs(root);
        return retmax;
    }
    public int dfs(TreeNode root){
        if(root==null){
            return 0;
        }
        int l = Math.max(0,dfs(root.left));//左树最大的单链
        int r = Math.max(0,dfs(root.right));//右树最大的单链
        retmax = Math.max(retmax,l+r+root.val);//左+右+root.val
        return root.val+Math.max(l,r);
    }
//    public void prev(TreeNode root){
//        if(root==null){
//            return;
//        }
//        prev(root.left);
//        tmpleft=0;
//        tmpright=0;
//        midtmp=0;
//        leftprev(root);
//        rightprev(root);
//        midprev(root);
//        prev(root.right);
//    }
//    //左根右
//    public void leftprev(TreeNode root){
//        if(root==null){
//            return;
//        }
//        leftprev(root.left);
//        tmpleft+=root.val;
//        retmax = Math.max(tmpleft,retmax);
//        leftprev(root.right);
//    }
//    public void rightprev(TreeNode root){
//        if(root==null){
//            return;
//        }
//        rightprev(root.right);
//        tmpright+=root.val;
//        retmax = Math.max(tmpright,retmax);
//        rightprev(root.left);
//    }
//    public void midprev(TreeNode root){
//        if(root==null){
//            return;
//        }
//        midtmp+=root.val;
//        retmax = Math.max(midtmp,retmax);
//        if(root.right!=null && root.left!=null){
//            if(root.right.val>root.left.val){
//                midprev(root.right);
//            }else {
//                midprev(root.left);
//            }
//        }else if(root.right!=null){
//            midprev(root.right);
//        }else if(root.left!=null){
//            midprev(root.left);
//        }
//    }

    public static void main2(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n+1];
        for (int i = 1; i <= n; i++) {
            arr[i] = in.nextInt();
        }

    }

    /**
     * 54. 螺旋矩阵
     * 给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
     *
     * “从左向右、从上向下、从右向左、从下向上” 四个方向循环打印。
     * 根据边界打印，即将元素按顺序添加至列表 res 尾部。
     * 边界向内收缩 1 （代表已被打印）。
     * 判断边界是否相遇（是否打印完毕），若打印完毕则跳出。
     *
     * @param matrix
     * @return
     */
    public List<Integer> spiralOrder(int[][] matrix) {
        int n = matrix.length,m = matrix[0].length;
        List<Integer> list = new ArrayList<>();
        int l = 0,r = m-1,up = 0,down = n-1;
        while(true){
            //左到右
            for (int i = l; i <= r; i++) {
                list.add(matrix[up][i]);
            }
            if(++up>down) break;
            //右边上到下
            for (int i = up; i <= down; i++) {
                list.add(matrix[i][r]);
            }
            if(--r<l) break;
            //右到左
            for (int i = r; i >= l; i--) {
                list.add(matrix[down][i]);
            }
            if(--down<up) break;
            //左边下到上
            for (int i = down; i >= up; i--) {
                list.add(matrix[i][l]);
            }
            if(++l>r) break;
        }
        return list;
    }
}
class look{
    public static boolean[] vis;
    public static int n;
    public static int N;
    public static int[] arr;
    public static int ret;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        arr = new int[n+1];
        for (int i = 1; i <= n; i++) {
            arr[i] = in.nextInt();
        }
        dfs(1);
    }
    public static void dfs(int pos){
        if(pos==n+1){
            //找到一种合法情况
            ret++;
            return;
        }
        for (int i = 1; i <= n; i++) {
            if(vis[i]){
                continue;
            }
            //我的诉求已经放过了,我只能排在他后面
            if(vis[arr[i]]){
                return;
            }
            vis[i] = true;
            dfs(pos+1);
            vis[i] = false;
        }
    }

}
